package com.shellSort;

import com.Sort;

/**
 * 希尔排序
 * 希尔排序更高效的原因：它权衡了子数组的规模和有序性。
 * 排序之初，各个步进分组都很短，排序之后子数组都是部分有序的，这两种情况都非常适合插入排序
 *
 * @param <Item>
 */
public class ShellSort<Item extends Comparable<Item>> extends Sort<Item> {
    /**
     * 交换不相邻的元素，以对数组的局部进行排序，并最终使用插入排序将局部有序的数组排序
     * 希尔排序的思想：使数组中任意间隔为h的元素都是有序的
     *
     * @param comparableArray
     */
    @Override
    public void sort(Item[] comparableArray) {
        int length = comparableArray.length;
        int step = 1;
        while (step < length / 3) {
            step = 3 * step;
        }
//        选择一个合适的步进，将数组进行分组插入排序
        int sortGroup = 0;
//        逐渐的合并分组，通过将步进减小到1，来合并分组
        while (step >= 1) {

//            当前进行插入排序的是哪一个分组，步进有多少，那么就有几个分组
            sortGroup = 0;

            while (sortGroup <= step) {
//          对每一个步进分组都进行插入排序
                stepInsertionSortSlow(comparableArray, length, step, sortGroup);
                sortGroup++;
            }

            step /= 3;  // 该递增序列会很大程度的影响排序速度
        }

    }


    /**
     * 有步进（step）的插入排序（流程说明版，效率极低）
     *
     * @param comparableArray 用于排序的数组
     * @param length          comparableArray的长度
     * @param step            按照这个步进，对 comparableArray 进行分组排序
     * @param sortGroup       当前排序的是哪一个分组
     */
    private void stepInsertionSortSlow(Item[] comparableArray, int length, int step, int sortGroup) {
//        以输入的步进，遍历该步进分组中未排序的元素，起始值为该步进分组的组号
        for (int unSortIndex = sortGroup; unSortIndex < length; unSortIndex += step) {
//            以输入的步进，便利该分组中已排序的元素，起始值为该步进分组的组号
            for (int sortedIndex = sortGroup; sortedIndex < unSortIndex; sortedIndex += step) {
//                要插入的元素比该步进分组中有序数组的下一个元素要小，说明应该将该元素插入在这个位置
                if (super.less(comparableArray[unSortIndex], comparableArray[sortedIndex])) {
//                    临时保存要插入的元素，因为会被覆盖
                    Item temp = comparableArray[unSortIndex];
//                    将要插入到有序分组中比要插入元素要大为起点，要插入元素原本所在位置为终点，输入的步进为步进，进行拷贝数组中的元素
                    for (int moveIndex = unSortIndex; moveIndex > sortedIndex; moveIndex -= step) {
//                        但是注意，这里是从倒数第二个移动到倒数第一个的方式，因为这样不用临时变量
                        super.exchange(comparableArray, moveIndex - step, moveIndex);
                    }
//                    将之前保存的要插入的元素插入到上一步移动数组中的元素空出来的位置
                    comparableArray[sortedIndex] = temp;
                }
            }
        }
    }
}
